package org.example.SolutionNew001;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class SubString02 {
    public static void main(String[] args) {
        SubString02 s = new SubString02();
        int[] nums=new int[]{1,3,1,2,0,5};
        System.out.println(Arrays.toString(s.maxSlidingWindow(nums, 3)));
    }

    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        int[] res=new int[n-k+1];
        Deque<Integer> deque = new LinkedList<Integer>();
        for(int i=0;i<n;i++){
            if(!deque.isEmpty()&&deque.peekFirst()<i-k+1) deque.pollFirst();
            while(!deque.isEmpty() &&nums[deque.peekLast()]<=nums[i]){
                deque.pollLast();
            }
            deque.addLast(i);
            if(i>=k-1){
                res[i-k+1]=nums[deque.peekFirst()];
            }
        }
        return res;
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n-k+1];

        //预处理
        int[] pre=new int[n];
        int[] suff=new int[n];
        //后一块的前缀
        for(int i=0;i<n;i++){
            if(i%k==0){
                pre[i]=nums[i];
            }else{
                pre[i]=Math.max(pre[i-1],nums[i]);
            }
        }

        //前一块的后缀
        for(int i=n-1;i>=0;i--){
            if(i==n-1||(i+1)%k==0){
                suff[i]=nums[i];
            }else{
                suff[i]=Math.max(suff[i+1],nums[i]);
            }
        }

        for(int i=0;i< res.length;i++){
            res[i]=Math.max(suff[i],pre[i+k-1]);
        }
        return res;
    }
}
